# 1617. 统计子树中城市之间最大距离
# 给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

# 一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

# 对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

# 请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

# 请注意，两个城市间距离定义为它们之间需要经过的边的数目。

#  

# 示例 1：

# **![img](./assets/p1.png)**

# 输入：n = 4, edges = [[1,2],[2,3],[2,4]]
# 输出：[3,4,0]
# 解释：
# 子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
# 子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
# 不存在城市间最大距离为 3 的子树。
# 示例 2：

# 输入：n = 2, edges = [[1,2]]
# 输出：[1]
# 示例 3：

# 输入：n = 3, edges = [[1,2],[2,3]]
# 输出：[2,1]


# 提示：

# 2 <= n <= 15
# edges.length == n-1
# edges[i].length == 2
# 1 <= ui, vi <= n
# 题目保证 (ui, vi) 所表示的边互不相同。


# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from typing import List, Dict, Tuple
from collections import defaultdict


class Solution:
    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:
        adjList = defaultdict(list)
        for a, b in edges:
            adjList[1 << (a - 1)].append(1 << (b - 1))
            adjList[1 << (b - 1)].append(1 << (a - 1))

        ans = [0] * (n - 1)
        for mask in range(1, 1 << n):
            unvisited, start, _ = self.bfs(mask & (-mask), adjList, mask)
            if unvisited: continue
            if (d := self.bfs(start, adjList, mask)[2]): ans[d - 1] += 1
        return ans
    
    def bfs(self, start: int, adjList: Dict[int, List[int]], mask: int) -> Tuple[int]:
        d = -1
        q = [start]
        while q:
            tmp, q = q, []
            for node in tmp:
                mask ^= node
                for child in adjList[node]:
                    if mask & child:
                        q.append(child)
            d += 1
        return mask, node, d
    
    
if __name__ == '__main__':
    # args = {"n": 4, "edges": [[1,2],[2,3],[2,4]]}
    args = {"n": 2, "edges": [[1,2]]}
    # args = {"n": 3, "edges": [[1,2],[2,3]]}
    start = time()
    print(Solution().countSubgraphsForEachDiameter(**args))
    print('='*40)
    print('耗时:', time()*1000 - start*1000, 'ms')